/**
 * 733. 图像渲染
 * https://leetcode.cn/problems/flood-fill/description/
 */
class Solution3 {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};
    boolean[][] check;
    int color, flag, m, n;

    public int[][] floodFill(int[][] image, int sr, int sc, int _color) {
        m = image.length;
        n = image[0].length;
        check = new boolean[m][n];
        color = _color;
        flag = image[sr][sc];

        image[sr][sc] = color;
        check[sr][sc] = true;
        dfs(image, sr, sc);

        return image;
    }

    public void dfs(int[][] image, int row, int col) {
        for (int i = 0; i < 4; i++) {
            int x = row + dx[i], y = col + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && image[x][y] == flag) {
                image[row][col] = color;
                check[row][col] = true;
                dfs(image, x, y);
            }
        }
    }
}